\chapter{Лекция 5. Финальное занятие по регулярным языкам}

\section{Лемма о накачке и критерий регулярности}

Когда мы хотим описать какой-то язык, хочется составить самую простую грамматику, т. е. не хочется для регулярного языка использовать контесктно-зависимую
грамматику. В с этим "инженерным" аспектом нам поможет так называемая лемма о накачке или лемма о разратании.

Пусть $R$ - регулярный язык, а $A$ - ДКА разбирающий язык $R$ и пусть у $A$ - $n$ состояний. Что будет если мы разбираем цепочку из более чем $n$ символов?
Тогда при работе автомата $A$ на этой цепочке он как минимум 2 раза пройдет через одно и то же состояние.

\begin{Lem}[О разрастании (о накачке)]
Пусть $R$ - регулярный язык, тогда $\exists p_R \in \mathbb{N}$ и $\forall w \in R : |w| \ge p_R \left[w = xyz \land |xy| \le p_R \land |y| \ge 1 \land xy^iy \in R\right]$
\end{Lem}

Пример, докажем, что язык правильных скобочных последовательностей не является регулярным, допустим, что язык регулярный, значит для него существует конечная
константа $p_R$, возьмем слово, которое начинается с $p_R$ открывающих скобок, очевидно, что $y$ состоит только из открывающихся скобок, а значит для произвольного
слова $xy^iz$ не верно, что оно принадлежит языку.

\paragraph{Внимание:} лемма о накачке работает только в одну сторону, существуют нерегулярные языки, для которых условие леммы о накачке выполнено.

Существует также критерий регулярности языка (критерий Майхилла-Нероуда). Пусть имеется автомат $A = \left(X, \Sigma, S, \sigma, F\right)$, в котором:
\begin{itemize}
\item $X$ - множество - входной алфавит

\item $\Sigma$ - алфавит состояний

\item $S \in \Sigma$ - начальное состояние

\item $F \subseteq \Sigma$ - множество финальных состояний

\item $\sigma : \Sigma\times X \rightarrow\Sigma$ - функция переходов
\end{itemize}

Можно дополнить функцию переходов до следующей функции $\sigma^* : \Sigma\times X^* \rightarrow \Sigma$, где $\sigma^*\left(S,\varepsilon\right) = S$ и
$\sigma^*\left(s, \alpha w\right) = \sigma^*\left(\sigma\left(s,\alpha\right),w\right)$, где $\alpha \in X$.

\begin{Def}
$R$ - правоинвариантное отношение, если и только если $\forall x,y \left[x R y \Rightarrow \forall z \left[xz R yz\right]\right]$
\end{Def}

Пусть $L$ - произвольный язык. Определим на $X^*$ бинарное отношение $~_L$. Элементы $x,y \in X^*$ вступают в отношение $~_L$, тогда и только тогда, когда для
$\forall z\in X^*$ $zx$ и $zy$ либо одновременно лежат в $L$ либо отдновременно не лежат в $L$.

Отношение $~_L$ является правоинвариантным и кроме того является отношением эквивалентности.

Рассмотрим пример, у нас есть язык с алфавитом ${0,1}$, в словах которого 1 не повторяется два раза подряд. Все множество $X^*$ рападается на классы:
\begin{enumerate}
\item все слова языка оканчивающиеся на 0 + пустое слово

\item все слова языка оканчивающиеся на 1

\item все слова содержащие пару единиц подряд
\end{enumerate}

Другой пример, язык правильных скобочных последовательностей. В этом разбиении уже бесконечное количество классов эквивалентности, а вместе с этим сразу
напрашивается критерий регулярности языка:

\begin{Th}[критерий Майхилла-Нероуда]
Язык регулярный тогда и только тогда, когда отношение $~_R$ имеет конечный индекс.
\end{Th}

\begin{Def}
Пусть имеется ДКА $A$, тогда $~_A$ - бинарное отношение на множестве $X^*$, такое что, $x~_Ay$ тогда и только тогда, когда
$\sigma^*\left(S,x\right) = \sigma^*\left(S,y\right)$. $~_A$ - правоинвариантное отношение эквивалентности.
\end{Def}

\begin{Proof}
\begin{enumerate}
\item Cледующие утверждения эквивалентны:

\item Язык $L$ распознается ДКА

\item Язык $L$ является объединением некоторого количества классов эквивалентности правоинвариантного отношения эквивалентности конечного индекса

\item Индекс отношения $~_L$ конечен
\end{enumerate}
1 $\Rightarrow$ 2: очевидно, если взять $~_A$, где $A$ - ДКА распознающий $L$. Т. е. если взять все классы эквивалентности соответсвующие состояний из $F$
автомата $A$, то получим весь язык $L$.

2 $\Rightarrow$ 3: покажем, что разбиение на классы эквивалентности по некоторому правоинвариантному отношению $~$ (на самом деле $~_A$ из предыдущего пункта)
является подразбиением разбиения по $~_L$. Для этого докажем, что $x~y \Rightarrow x~_Ly$. Для $\forall z$ $xz~yz$ (из правоинвариантности $~$), положим $xz \in L$,
но $L$ является объединением классов эквивалентности по $~$, следовательно и $yz$ лежит в $L$. Аналогично, если $xz \not\in L$, получаем $yz \not\in L$. Собирая все
вместе получаем, что $xz~yz \Rightarrow xz~_Lyz$, что и требовалось доказать.

3 $\Rightarrow$ 1: Пусть имеется $L$ и отношение $~_L$ имеет конечный индекс. Построим КА, в качестве состояний автомата выступают классы эквивалентности по
отношению $~_L$. Начальное состояние - класс эквивалентности включающий пустую цепочку. Множество финальных состояний - все классы эквивалентности входящие в язык.
Функция переходов определяется очевидным образом, т. е. если $[w]$ - класс эквивалентности включающий цепочку $w$, а $a$ - символ входного алфавита, тогда
$\sigma\left([w],a\right) \rightarrow [wa]$.
\end{Proof}

\section{Минимизация}

В минимальном по числу состояний автомате допускающем язык $L$ ровно столько состояний, сколько существует классов эквивалентности по отношению $~_L$
(см. доказатиельство выше). Осталось убедится, что таких автоматов не существует много, а на самом деле существует только один, но это очевидно так как
классы эквивалентности по $~_A$ совпадают с классами эквивалентности по $~_L$, для любого минимального $A$, а переходы очевидно также совпадают. Остается
понять как этот автомат построить?

\paragraph{Минимизация ДКА} Для минимизации требуется отсыкивать эквивалентные состояния внутри автомата.
